/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class DivisorGame {
	/**
	 * 超时
	 * 
	 * @param N
	 * @return
	 */
	public boolean divisorGame2(int N) {
		if (N == 1) {
			return false;
		}
		for (int i = 1; i < N; i++) {// 找因子
			if (N % i == 0) {
				boolean enmySucc = divisorGame(N - i);
				if (!enmySucc) {
					return true;
				}
			}
		}
		return false;
	}

	public boolean divisorGame(int N) {
		boolean[] dp = new boolean[N + 1];
		dp[1] = false;
		for (int i = 2; i < dp.length; i++) {
			for (int j = 1; j < i; j++) {
				if (i % j == 0) {
					boolean enSucc = dp[i - j];
					if (!enSucc) {
						dp[i] = true;
						break;
					}
				}
			}
		}
		return dp[N];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
